package DP;

/**
 * https://leetcode-cn.com/problems/coin-change-2/
 */
public class DecodeWays {

    /**
     *  转移公式：
     */
    public int numDecodings(String s) {
        char[] ss = s.toCharArray();
        if(ss.length == 0){
            return 0;
        }
        if(ss[0] == '0'){
            return 0;
        }

        int[] dp = new int[ss.length + 1];

        dp[0] = 1;
        int j;
        for(int i=1; i <= ss.length; i++){
            dp[i]=0;
            if(ss[i-1] >= '1' && ss[i-1] <= '9'){
                dp[i] = dp[i-1];
            }
            if(i > 1){
                j = 10 * (ss[i-2] - '0') + (ss[i-1] - '0');
                //如果往前的2个字符是10--26 的，那就是可以有2中情况
                if(j >= 10 && j<= 26){
                    //必须是10，因为上面没加上，另外，为什么是 i-2，是因为要完整的2个字母
                    dp[i] = dp[i] + dp[i-2];
                }
            }
        }

        return dp[ss.length];
    }


    public static void main(String[] args){
        DecodeWays d = new DecodeWays();
//        d.numDecodings("12");
        System.out.println(d.numDecodings("110"));
    }


}
